﻿namespace LeetCodeProject._0001_1000._001_100._91_100._095;

public class Solution
{
    public IList<TreeNode> GenerateTrees(int n)
    {
        if (n == 0)
            return new List<TreeNode>(0);
        var result = Generate(1, n + 1);
        return result;
    }

    private List<TreeNode> EmptyResults = new List<TreeNode>(1) { null };

    private IList<TreeNode> Generate(int i, int k)
    {
        if (i == k)
            return EmptyResults;
        var result = new List<TreeNode>();
        for (int j = i; j < k; j++)
        {
            var leftNode = Generate(i, j);
            var rightNode = Generate(j + 1, k);
            foreach (var left in leftNode)
            {
                foreach (var right in rightNode)
                {
                    result.Add(new TreeNode(j) { left = left, right = right });
                }
            }
        }

        return result;
    }
}